package UnitTest;

import java.util.LinkedList;

/**
 * @Auther: Administrator
 * @Date: 2019/9/6/006 19 22
 * @Description:
 */
public class FindLCA {

    static final int maxNumOfChilds = 10;
    //使用两个链表来保存根节点到所求节点的路径
    static LinkedList list1 = new LinkedList();
    static LinkedList list2 = new LinkedList();

    public static void main(String args[]) {
        TreeNode1 A = new TreeNode1();
        A.value = 'A';
        TreeNode1 B = new TreeNode1();
        B.value = 'B';
        TreeNode1 C = new TreeNode1();
        C.value = 'C';
        TreeNode1 D = new TreeNode1();
        D.value = 'D';
        TreeNode1 E = new TreeNode1();
        E.value = 'E';
        TreeNode1 F = new TreeNode1();
        F.value = 'F';
        TreeNode1 G = new TreeNode1();
        G.value = 'G';
        TreeNode1 H = new TreeNode1();
        H.value = 'H';
        TreeNode1 I = new TreeNode1();
        I.value = 'I';
        TreeNode1 J = new TreeNode1();
        J.value = 'J';
        A.childs = new TreeNode1[]{B, C};
        B.childs = new TreeNode1[]{D, E};
        D.childs = new TreeNode1[]{F, G};
        E.childs = new TreeNode1[]{H, I, J};
        /*
                A
               / \
              B   C
             /  \
             D    E
           / \   / | \
          F   G  H I  J
         */

        //找F,H节点的LCA
        TreeNode1 lca = findLCA(A, F, H);
        System.out.println(lca);
    }


    private static TreeNode1 findLCA(TreeNode1 root,TreeNode1 node1, TreeNode1 node2) {
        getPathFromRootToNode(node1, root, list1);
        getPathFromRootToNode(node2, root, list2);
        int index = 0;
        int length1 = list1.size();
        int length2 = list2.size();
        int sub = length1 > length2 ? length1 - length2 : length2 - length1;
        if (length2 > length1) {
            LinkedList temp = list1;
            list1 = list2;
            list2 = temp;
        }
        while (index != length2 - 1) {
            if (((TreeNode1) list1.get(index + sub)).value == ((TreeNode1) list2.get(index)).value) {
                return (TreeNode1) list2.get(index);
            } else {
                index++;
            }
        }
        return null;
    }

    private static boolean getPathFromRootToNode(TreeNode1 node, TreeNode1 currentRoot, LinkedList list) {
        if (node.value == currentRoot.value) {
            return true;
        }
        list.push(currentRoot);

        boolean found = false;

        TreeNode1[] childs = currentRoot.childs;
        if (childs != null && childs.length > 0) {
            for (int i = 0; i < childs.length; i++) {
                if (found) {
                    break;
                } else {
                    found = getPathFromRootToNode(node, childs[i], list);
                }
            }
        }
        if (!found) {
            list.pop();
        }

        return found;
    }


}


//树结构定义
class TreeNode1 {
    char value;
    TreeNode1 childs[];

    @Override
    public String toString() {
        return "TreeNode1 [value=" + value + "]";
    }

}
